Marking documents with machine-readable characters to facilitate automatic document recognition using character recognition systems is well known in the art. In many industries, labels are printed with machine-readable symbols, often referred to as barcodes, and are applied to packages and parcels. The machine-readable symbols on the labels typically carry information concerning the packages and parcels that is not otherwise evident from the packages and parcels themselves.
For example, one-dimensional barcode symbols, such as those following the well-known Universal Product Code (UPC) specification, regulated by the Uniform Code Council, are commonly used on machine-readable labels due to their simplicity. A number of other one-dimensional barcode symbol specifications have also been proposed, such as for example POSTNET that is used to represent ZIP codes. In each case, the one-dimensional barcode symbols governed by these specifications have optimizations suited for their particular use. Although these one-dimensional barcode symbols are easily scanned and decoded, they suffer disadvantages in that they are only capable of encoding a limited amount of information.
To overcome the disadvantages associated with one-dimensional barcode symbols, two-dimensional machine-readable symbols have been developed to allow significantly larger amounts of information to be encoded. For example, the AIM Uniform Symbology Specification For PDF417 defines a two-dimensional barcode symbol format that allows each barcode symbol to encode and compress up to 1108 bytes of information. Information encoded and compressed in each barcode symbol is organized into a two-dimensional data matrix including between 3 and 90 rows of data that is book-ended by start and stop patterns. Other two-dimensional machine-readable symbol formats such as, for example, AZTEC, QR-Code and MaxiCode have also been considered.
Although two-dimensional machine-readable symbols allow larger amounts of information to be encoded, an increase in sophistication is required in order to read and decode such two-dimensional symbols. In fact decoding two-dimensional symbols often requires relatively large amounts of computation. As a result, it is desired to ensure that two-dimensional symbols are read properly before the decoding process commences. This is particularly important in high-volume environments.
To ensure that two-dimensional symbols are in fact read properly, finder patterns are commonly embedded in two-dimensional machine-readable symbols. The finder patterns allow the two-dimensional symbols to be correctly delineated and oriented so that the data encoded in the two-dimensional symbols can be properly extracted and decoded. For example, SR-Code makes use of square symbols, each comprising a grid of black or white square modules, and having three square finder patterns positioned at respective ones of the bottom left, top left and top right corners of the symbol. Each finder pattern consists of a solid square of black modules surrounded by a square ring of white modules, which is in turn surrounded by a square ring of black modules. The outward-facing sides of the square ring of black modules form a symbol corner. Additional lines of white modules border the inward-facing sides of the square ring of black modules to separate the finder pattern from the data encoded in the symbol.
Depending on the environment and the scanning equipment used to capture images of the two-dimensional symbols being read, the ease by which finder patterns are located in captured images can vary significantly. As a result, a number of techniques for locating finder patterns and decoding two-dimensional symbols have been considered.
For example, U.S. Patent Application Publication No. 2004/0020989 to Muramatsu discloses a method for reading a QR-Code symbol. According to this method, each read QR-Code symbol is searched for an approximate 1:1:3:1:1 run of black and white pixels in horizontal, vertical and inclined directions and candidate finder pattern origins are accorded respective evaluation values. The lengths of the candidate finder pattern runs are calculated and an error between the 1:1:3:1:1 standard run is calculated. Those runs with an error above a predetermined threshold are deleted as candidates. Those runs with the smallest errors are given a higher evaluation. Center coordinates of the evaluation finder patterns are determined by comparing the widths and centers of proximate finder pattern candidates. From these comparisons, highest evaluation finder patterns are located and their center coordinates determined. The cell size is determined from the finder patterns by dividing the average finder pattern width by seven (7).
The orientation of the QR-Code symbol is determined by first linking the finder patterns' center coordinates to form a triangle, and deeming the coordinate not on the longest line of the triangle as the top left finder pattern. The bottom left and top right finder patterns are oriented by dividing the space around the top left finder pattern into quadrants, and determining in which adjacent quadrants, relative to the top left finder pattern, the other two finder patterns are located.
The alignment pattern is located by first detecting the rotational angle of the QR-Code symbol from the finder pattern and finding the intersection point of lines from the centers of the top right and bottom left finder patterns parallel to respective edges of the symbol. The center of the alignment pattern is considered to be three (3) cells inward (i.e. towards the top left finder pattern) from the intersection point. To confirm the alignment pattern, a 5×5 template is compared to a retrieval range having a center at the deemed alignment pattern center. Matching is conducted by summing absolute values of differences between the pixel values of all of the pixels forming the template and the pixel values of pixels in the retrieval range. Sequentially shifting one pixel over all pixels in the retrieval range to determine minimum differences in pixel values enables a more accurate determination of the alignment pattern center.
The version of the QR-Code symbol is determined by calculating the number of cells between finder patterns. A quotient is obtained by dividing the average of the distances between the finder patterns by the cell size determined as described above from the pattern width. A light/dark threshold is calculated by finding the maximum and minimum pixel values along a line connecting the top right and bottom left finder patterns, and averaging the two. A conversion coefficient is then calculated for converting points from a standard QR-Code symbol to an input image. A linear interpolation of four adjacent pixels to the determined center of a cell is conducted to calculate a pixel value at the module center.
U.S. Pat. No. 6,758,399 to Brunelli et al. discloses a method of detecting an optical code such as a QR-Code symbol, and correcting for distortion. The method first determines a binary threshold value and finds regions of interest by locating areas with high-brightness variations. It is assumed that the symbol orientation is known, and the vertices are located using the methods outlined in the AIM Global International Symbology Specification for QR-Code. Using the located vertices, the optical code is localized and extracted from the image for further processing. At this point, the timing patterns and number of symbol elements are located in the optical code. Based on the number of symbol elements, an ideal grid is generated and a transformation between the ideal grid and the input symbol is calculated. From the location of the transformed vertices of the ideal grid, brightness values are acquired and binarized using the threshold value.
Although the above references disclose methods of locating and extracting data from QR-Code symbols in a digital image, symbol orientation is either taken for granted or computationally expensive. Furthermore, these disclosed methods do not address situations in which the symbol is either skewed or pitched in the digital image. It is therefore an object of the invention to provide a novel method and apparatus for locating and decoding two-dimensional symbols in digital image.